#include "cfg.h"

/*
	creates a linked list of instrcutions
	and numbers the nstrcutions
*/
int number_instrs (instr_node ** instr_head, simple_instr *inlist) {
	int count = 0;
	simple_instr * instr = inlist;
	instr_node * lastinstr = NULL;

	while(instr) {
		instr_node * tempinstr = (instr_node *) malloc(sizeof(instr_node));
		tempinstr->number = count++;
		tempinstr->next = NULL;
		tempinstr->previous = lastinstr; 
		tempinstr->instr = instr;
		tempinstr->block = NULL;

		if(*instr_head == NULL) {
			*instr_head = tempinstr;
		}
		else {
			lastinstr->next = tempinstr;
		}	

		lastinstr = tempinstr;
		instr = instr->next;
	}
	return count;
}

/*
	finds basic blocks
	supports
		- conditional and uncondition branch
		- ret statements
		- MBR statements
*/
int find_basic_block (basic_block_node ** basic_block_head, instr_node * instr_head) {
	instr_node * current_chain = NULL;
	instr_node * current_instr = instr_head;
	int basic_block_number = 0;
	basic_block_node * lastblock = NULL;
	basic_block_node * current_basic_block = (basic_block_node *) malloc(sizeof(basic_block_node));

	int instructionsCount = 0;

	/* Entry block */
	current_basic_block->start = NULL;
	current_basic_block->end = NULL;
	current_basic_block->total_instrs = 0;
	current_basic_block->number = basic_block_number++;
	current_basic_block->next = NULL;
	current_basic_block->previous = NULL;
	current_basic_block->dom = NULL;
	current_basic_block->predecessor = NULL;
	current_basic_block->successor = NULL;
	current_basic_block->idom = NULL;

	*basic_block_head = current_basic_block;
	lastblock = current_basic_block;

	current_basic_block = (basic_block_node *) malloc(sizeof(basic_block_node));
	current_basic_block->start = NULL;
	current_basic_block->next = NULL;
	/* end of Entry Block */

	
	while(current_instr) {
		/* detect if it is a new basic block */
		if(current_basic_block->start == NULL) {
			/* store the start of the basic block */
			current_basic_block->start = current_instr;
			instructionsCount = 0;
		}

		instructionsCount++;

		/* update the basic block property of the current instruction */
		current_instr->block = current_basic_block;
	
		switch(simple_op_format(current_instr->instr->opcode)) {
			case BASE_FORM: {
				// find if the current instruction is RET_OP
				if(current_instr->instr->opcode != RET_OP)
				{
					current_instr = current_instr->next;
					continue;	
				}
			}
			case BJ_FORM: { }
			case MBR_FORM: {
				current_basic_block->number = basic_block_number++;
				current_basic_block->end = current_instr;
				current_basic_block->total_instrs = instructionsCount;
				current_basic_block->previous = lastblock;
				current_basic_block->next = NULL;
				current_basic_block->predecessor = NULL;
				current_basic_block->successor = NULL;
				
				// link it to the link list and move the pointer
				lastblock->next = current_basic_block;
				lastblock = current_basic_block;

				current_basic_block = (basic_block_node *) malloc(sizeof(basic_block_node));
				current_basic_block->start = NULL;
				current_basic_block->end = NULL;
				current_basic_block->next = NULL;
				break;
			}
			case LABEL_FORM: {
				lastblock->next = current_basic_block;

				if(current_basic_block->start != current_instr) {
					current_basic_block->previous = lastblock;
					current_basic_block->number = basic_block_number++;
					current_basic_block->end = current_instr->previous;
					current_basic_block->total_instrs = instructionsCount - 1;
					current_basic_block->predecessor = NULL;
					current_basic_block->successor = NULL;
					lastblock = current_basic_block;
					current_basic_block = (basic_block_node *) malloc(sizeof(basic_block_node));	
					current_basic_block->predecessor = NULL;
					current_basic_block->successor = NULL;
					instructionsCount = 1;
				} 
				
				current_basic_block->number = basic_block_number;
				current_basic_block->start = current_instr;
				current_basic_block->end = NULL;
				current_basic_block->next = NULL;
				current_basic_block->previous = lastblock;
				break;
			}
		}
		current_instr = current_instr->next;
	}

	lastblock->next = (basic_block_node *) malloc(sizeof(basic_block_node));
	lastblock->next->previous = lastblock;
	lastblock = lastblock->next;

	lastblock->number = basic_block_number;
	lastblock->predecessor = NULL;
	lastblock->successor = NULL;
	lastblock->total_instrs = 0;
	lastblock->next = NULL;
	lastblock->start = NULL;
	lastblock->end = NULL; 
	return basic_block_number + 1;
}

/* 
	finds predecessors and successors
*/
void find_predecessors(basic_block_node * cfg_head) {
	basic_block_node * block1 = NULL;
	basic_block_node * block2 = NULL;
	//block_ptr * current_predecessor = NULL;
	block_ptr * current_successor = NULL;
	int total_successors = 0;
	int total_predecessors = 0;

	for(block1 = cfg_head; block1 != NULL; block1 = block1->next)
	{
		block1->predecessor = NULL;
		block1->total_predecessors = 0;
	//	current_predecessor = NULL;
		if(block1->start != NULL && simple_op_format(block1->start->instr->opcode) == LABEL_FORM) {
			for(block2 = cfg_head; block2 != NULL; block2 = block2->next) {
				/* check if another block's exist instruction is a JMP and it has the same target */
				if(block2->end != NULL && simple_op_format(block2->end->instr->opcode) == BJ_FORM) {
					if(block2->end->instr->u.bj.target == block1->start->instr->u.label.lab)
					{
						insert_block_ptr(&block1->predecessor, /* &current_predecessor, */ block2);
						block1->total_predecessors++;
					}
				}
				else if(block2->end != NULL && simple_op_format(block2->end->instr->opcode) == MBR_FORM) {
					int i = 0;
					if(block1->start->instr->u.label.lab == block2->end->instr->u.mbr.deflab) {
						insert_block_ptr(&block1->predecessor, /* &current_predecessor, */ block2);
                        block1->total_predecessors++;
					} else
					for(i=0; i<block2->end->instr->u.mbr.ntargets; i++) {
						if(block1->start->instr->u.label.lab == block2->end->instr->u.mbr.targets[i])
						{
							insert_block_ptr(&block1->predecessor, /* &current_predecessor, */  block2);
							block1->total_predecessors++;
							break;	
						}
					}
				}	
			}
		} 
		
		if(block1->number == 1) {
			insert_block_ptr(&block1->predecessor, /* &current_predecessor,*/  block1->previous);
			block1->total_predecessors++;
		}

		if(block1->previous != NULL && block1->start != NULL && block1->start->previous!=NULL 
				&& block1->start->previous->instr->opcode!=JMP_OP 
				&& block1->start->previous->instr->opcode!=MBR_OP 
				&& block1->start->previous->instr->opcode!=RET_OP) {

			insert_block_ptr(&block1->predecessor,/* &current_predecessor, */ block1->previous);
			block1->total_predecessors++;
		}

		/*
			Exit Block is a special case. We need to find the predecessors for exit block
			by traversing to see if any other block has a ret
		*/
		if(block1->next == NULL) {
			for(block2 = cfg_head; block2!=NULL; block2 = block2->next) {
				if(block2->end != NULL && block2->end->instr->opcode == RET_OP) {
					insert_block_ptr(&block1->predecessor, /* &current_predecessor, */ block2);
					block1->total_predecessors++;
				}	
			}
		}
		
		block1->successor = NULL;
		block1->total_successors = 0;
		if(block1->end != NULL && simple_op_format(block1->end->instr->opcode) == MBR_FORM) {
			for(block2 = cfg_head; block2 != NULL;  block2 = block2->next) {
				if(block2->end != NULL && block1->end->instr->u.mbr.deflab == block2->start->instr->u.label.lab) {
					insert_block_ptr(&block1->successor, block2);
                     block1->total_successors++;
				} else {
					int i=0;
					for(i=0; i < block1->end->instr->u.mbr.ntargets; i++) {
						if(block2->end != NULL && block1->end->instr->u.mbr.targets[i] == block2->start->instr->u.label.lab) {
							insert_block_ptr(&block1->successor, block2);
                       		block1->total_successors++;
						}
					}
				}
			}
		}
		else if(block1->end != NULL && simple_op_format(block1->end->instr->opcode) == BJ_FORM) {
			if(block1->end->instr->opcode!=JMP_OP) {
				insert_block_ptr(&block1->successor, block1->next);
				block1->total_successors++;
			}
			for(block2 = cfg_head; block2 != NULL; block2 = block2->next ) {
				if(block2->start != NULL && simple_op_format(block2->start->instr->opcode) == LABEL_FORM) {
					if(block1->end->instr->u.bj.target == block2->start->instr->u.label.lab) 
					{
						insert_block_ptr(&block1->successor, block2);
						block1->total_successors++;
					}	
				}
			}
		} else {
			if(block1->next != NULL) {
				insert_block_ptr(&block1->successor, block1->next);
				block1->total_successors++;
			}
		}	

	}
}

/*
	this function finds the dominators for each block
	and saved them in basic_block_node->dom
*/
void find_dominators(basic_block_node * cfg, int maxdominators) {
    basic_block_node * current_block = cfg->next;
    boolean changed = TRUE;

    if(cfg == 0) return;

    cfg->dom = new_bit_vector(maxdominators);
    set_all_bits(cfg->dom, FALSE);
    set_bit(cfg->dom, 0, TRUE);

	while(current_block->next) {
		// initialize the dom bit vector
		current_block->dom = new_bit_vector(maxdominators);
		// assume all blocks as its dominators
		set_all_bits(current_block->dom, TRUE);
		current_block = current_block->next;
    }

    current_block->dom = new_bit_vector(maxdominators);
    set_all_bits(current_block->dom, FALSE);
	
	while(changed) {
		changed = FALSE;
		current_block = cfg->next;
		while(current_block->next) {
			block_ptr * current_predecessor = current_block->predecessor;
			bit_vector * old_dom = new_bit_vector(maxdominators);

			// the intersection vector is intialized to TRUE
			bit_vector * intersection = new_bit_vector(maxdominators);
			set_all_bits(intersection, TRUE);

			// keeping a copy of dom in old_dom for comparison
			copy_bits(old_dom, current_block->dom);

			// find the intersection with predecessor's dom
			if(current_predecessor == NULL) {
				set_all_bits(intersection, FALSE);
				//printf("block # %d does not have a predcessor", current_block->number);
			} else

//			printf("\nBlock # %d\n", current_block->number);
			while(current_predecessor) {
//				printf("\tpredecessor # %d ", current_predecessor->block->number);
//				fprint_bits(stdout, current_predecessor->block->dom, fprint_bit);
//				printf("\n");	
				and_bits(intersection, current_predecessor->block->dom);
				current_predecessor = current_predecessor->next;
			}	
			copy_bits(current_block->dom, intersection);
			set_bit(current_block->dom, current_block->number, TRUE);

			//printf("\nblock # %d", current_block->number);
			//fprint_bits(stdout, intersection, fprint_bit);

			if(!bits_are_equal(current_block->dom, old_dom)) 
				changed = TRUE;	
			current_block = current_block->next;
		}
	}
}

/*
	this function find the idominators
	and stores them in basic_block_node->idom
*/
void find_idominators(basic_block_node * cfg, int blocknumber) {
	basic_block_node * current_block = cfg;
	basic_block_node * find_block;
	int index1;
	int index2;

	while(current_block) {
		// initialize the idom bit vector
		current_block->idom = new_bit_vector(blocknumber);
		current_block->pdom = new_bit_vector(blocknumber);
		// copy dom to proper dom
		copy_bits(current_block->pdom, current_block->dom);
		
		// make dom to a proper dom by removing the self block
		set_bit(current_block->pdom, current_block->number, FALSE);
		
		// copy proper dom to idom
		copy_bits(current_block->idom, current_block->pdom);
		
		current_block = current_block->next;
	}


	current_block = cfg;
	while(current_block) {
		for(index1 = 0; index1 < blocknumber; index1++) {
			if(get_bit(current_block->pdom, index1))
			for(index2 = 0; index2 < blocknumber; index2++) {
				if(index1 == index2) continue;
				if(get_bit(current_block->pdom, index2)) {
					// find if index2 is a dominator of index1
					find_block = cfg;
					while(find_block->number != index1) find_block = find_block->next;
					if(get_bit(find_block->pdom, index2))
						set_bit(current_block->idom, index2, FALSE);
				}	
			}
		}
	
		current_block = current_block->next;
	}

	if(cfg!=NULL && cfg->next != NULL)
		set_bit(cfg->next->idom, 0, TRUE);
}
